/** 正确的方法，利用了BST的特性 O(n)
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        travel(root);
        return root;
    }
    void travel(TreeNode* root) {
        if(!root) return;
        travel(root -> right);
        sum += root -> val;
        root -> val = sum;
        travel(root -> left);
        return;
    }
};

/** 傻方法，brute force，O(3n)
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    priority_queue<int, vector<int>, less<int>> q;
    unordered_map<int, int> m;
    TreeNode* convertBST(TreeNode* root) {
        if(!root) return NULL;
        push_q(root);
        int sum = q.top();
        m[q.top()] = sum;
        int pre = sum;
        q.pop();
        while(!q.empty())
        {
            sum += q.top();
            if(q.top() != pre)
            {
                m[q.top()] = sum;
                pre = q.top();
            }
            q.pop();
        }
        set_tree(root);
        return root;
    }
    void push_q(TreeNode* root) {
        if(!root) return;
        q.push(root -> val);
        push_q(root -> left);
        push_q(root -> right);
        return;
    }
    void set_tree(TreeNode* root) {
        if(!root) return;
        root -> val = m[root -> val];
        set_tree(root -> left);
        set_tree(root -> right);
        return;
    }
};
